[Swift] 爆速計算ライブラリ Surge を使う

Accelerate.Framework + Swift

Accelerate フレームワークは線形代数の計算を始めとし、音声、信号処理に応用の効くフーリエ変換や画像処理などでハイパフォーマンスな計算処理を提供します。

このフレームワーク内では OS X / iPhone で用いられている Intel, ARM などの CPU の SIMD 命令を用いて計算が最適化されています。

Accelerate フレームワーク自体は iOS のフレームワークのなかでも比較的低レイヤな位置づけであるため、フレームワークを直接叩くような実装を開発者が行うことはまれです。

とはいえ、重量級の計算をアプリケーションのロジック部で行う際に、SIMD による最適化の恩恵が得られるにも関わらず、それを行わないのは宝の持ち腐れと言えます。

Surge はこの低レイヤな位置づけにある Accelerate フレームワークを馴染み深い関数名でラップすることで配列を中心とした計算を扱いやすくしてくれています。

導入方法

Alamofire の導入方法と同様に git submodule を用いて導入します。今回はテストターゲットに導入してみましょう。

まず、コマンドラインでプロジェクトのルートディレクトリに移動してください。

Surgeを入れたいプロジェクトに git が入っていない場合、git init で git リポジトリを初期化してください。

その後、サブモジュールを以下のように追加します。

$ git submodule add https://github.com/mattt/Surge

次に Surge フォルダを Finder で開き、Surge.xcodeproj ファイルをプロジェクトの Project Navigator にドラッグ&ドロップしてください。

Surge のプロジェクトファイルが上の画面のようにインポートされます。

次に Surge を入れたいプロジェクトのアイコンをクリック、Targets の中から Surge を入れたいターゲットをクリックします。ここではテストターゲットに入れます。

ターゲットをクリックした後、上部の Build Phases をクリックし、Target Dependencies の + ボタンをクリックします。

どのコンポーネントをリンクするか選択を行うウィンドウが表示されます。Surge を選択し、Addボタンを押してターゲットにフレームワークを入れます。

左上の + ボタンをクリックして新たに Build Phase を作成します。

作成した Build Phase を Copy Frameworks 等適当な名前にリネームした上で Destination に Frameworks を選択し、下の + ボタンをクリックします。

目的の Surge をクリックしてフレームワークを導入します。

関数の紹介

Surge の各 swift ファイルにトップレベルで定義された関数を紹介します。

Arithmetic.swift

関数	役割	Swiftを用いた計算法
sum(x: [Double]) -> Double	総和	reduce(x, 0.0, +)
add(x: [Double], y: [Double]) -> [Double]	和	map(Zip2(x, y), +)
mul(x: [Double], y: [Double]) -> [Double]	積	map(Zip2(x, y), *)
div(x: [Double], y: [Double]) -> [Double]	商( x[i] / y[i] )	map(Zip2(x, y), /)
mod(x: [Double], y: [Double]) -> [Double]	剰余（ x[i] / y[i] の余り 結果は正）	map(Zip2(x, y), fmod)
remainder(x: [Double], y: [Double]) -> [Double]	剰余（ x[i] / y[i] の余り 結果はxの符号と同じ）	map(Zip2(x, y), remainder)
sqrt(x: [Double]) -> [Double]	平方根	x.map(sqrt)

Auxiliary.swift

関数	役割	Swiftを用いた計算法	備考
abs(x: [Double]) -> [Double]	絶対値	x.map(abs)
ceil(x: [Double]) -> [Double]	小数点切り上げ	x.map(ceil)
copysign(sign: [Double], magnitude: [Double]) -> [Double]	magnitude[i] の絶対値に sign[i] の符号をつける	map(Zip2(magnitude, sign), copysign)	現在引数の意味が逆さまになっており、pull req 中
floor(x: [Double]) -> [Double]	床関数	x.map(floor)
rec(x: [Double]) -> [Double]	逆数	x.map{a in 1 / a}
round(x: [Double]) -> [Double]	四捨五入	x.map(round)
trunc(x: [Double]) -> [Double]	端数切り捨て	x.map(trunc)

Exponential.swift

関数	役割	Swiftを用いた計算法	備考
exp(x: [Double], y: [Double]) -> [Double]	自然対数の累乗	y.map(exp)	x の引数はメモリバッファ的な意味のみであり、pull req 中
exp2(x: [Double], y: [Double]) -> [Double]	2の累乗	y.map(exp2)	x の引数はメモリバッファ的な意味のみであり、pull req 中
log(x: [Double]) -> [Double]	自然対数	x.map(log)
log2(x: [Double]) -> [Double]	2を底とする対数	x.map(log2)
log10(x: [Double]) -> [Double]	10を底とする対数	x.map(log10)

FFT.swift

func fft(input: [Double]) -> [Double]

この関数は高速フーリエ変換(Fast Fourier Transform)を行います。iOS に於ける高速フーリエ変換についての詳細は Qiita に詳細にまとめておられる方がいらっしゃるのでそちらを御覧ください。

Hyperbolic.swift

関数	役割	Swiftを用いた計算法
sinh(x: [Double]) -> [Double]	sinh	x.map(sinh)
cosh(x: [Double]) -> [Double]	cosh	x.map(cosh)
tanh(x: [Double]) -> [Double]	tanh	x.map(tanh)
asinh(x: [Double]) -> [Double]	asinh	x.map(asinh)
acosh(x: [Double]) -> [Double]	acosh	x.map(acosh)
atanh(x: [Double]) -> [Double]	atanh	x.map(atanh)

Power.swift

関数	役割	Swiftを用いた計算法
pow(x: [Double], y: [Double]) -> [Double]	累乗	map(Zip2(x, y), pow)

Trigonometric.swift

関数	役割	Swiftを用いた計算法
sin(x: [Double]) -> [Double]	sin	x.map(sin)
cos(x: [Double]) -> [Double]	cos	x.map(cos)
tan(x: [Double]) -> [Double]	tan	x.map(tan)
asin(x: [Double]) -> [Double]	asin	x.map(asin)
acos(x: [Double]) -> [Double]	acos	x.map(acos)
atan(x: [Double]) -> [Double]	atan	x.map(atan)

ベンチマークをとってみた

このフレームワークの使用例も兼ねて、大きなサイズの配列計算についてベンチマークをとり、Surge で扱った場合と、swift の標準ライブラリで扱った場合を比較しました。

ベンチマークに最適なパフォーマンステスト環境が Xcode6 からは標準で備わっており、そちらを今回は用いました。

本記事にテストコードも記載していますが、手っ取り早く確認されたい方はこちらにソースコードを上げましたので

$ git clone https://github.com/UsrNameu1/SurgeBenchmark && cd SurgeBenchmark && git submodule init && git submodule update

してみてください。

ベンチマーク環境

• iPhone5s 64GB
• iOS 8.1

ベンチマーク結果

総和

テストコード

class SurgeSumTests: XCTestCase {

    var doubleList: [Double] = [Double]()

    override func setUp() {
        super.setUp()
        let largeNumber = 100
        let list = [Int](1...largeNumber)
        doubleList = list.map {i in Double(i)}
    }

    func testSurgeSum() {
        self.measureBlock { // Surge フレームワークによる配列の総和
            let result = Surge.sum(self.doubleList) // 総和
        }
    }

    func testNativeSum() {
        self.measureBlock { // Swift 標準ライブラリを用いた配列の総和
            let result = reduce(self.doubleList, 0.0, +)
        }
    }
}

largeNumber	Swift	Surge	swift / surge
100	0.002sec (5% STDEV)	0.000sec (64% STDEV)	????
1000	0.016sec (5% STDEV)	0.000sec (97% STDEV)	????
10000	0.158sec (2% STDEV)	0.000sec (59% STDEV)	????
100000	1.572sec (2% STDEV)	0.000sec (44% STDEV)	????
1000000	15.582 sec (1% STDEV)	0.001 sec (10% STDEV)	15582.000

和

テストコード

class SurgeAddTests: XCTestCase {

    var doubleList: [Double] = [Double]()

    override func setUp() {
        super.setUp()

        let largeNumber = 1000000
        let list = [Int](1...largeNumber)
        doubleList = list.map {i in Double(i)}
    }

    func testSurgeAdd() {
        self.measureBlock { // Surge フレームワークによる配列同士の和
            let add = Surge.add(self.doubleList, self.doubleList) 
        }
    }

    func testNativeAdd() {
        self.measureBlock { // Swift 標準ライブラリを用いた配列同士の和
            let add = map(Zip2(self.doubleList, self.doubleList), +)
        }
    }
}

largeNumber	Swift	Surge	swift / surge
100	0.007sec (8% STDEV)	0.001sec (41% STDEV)	7.000
1000	0.066sec (4% STDEV)	0.016sec (17% STDEV)	4.125
10000	0.643sec (1% STDEV)	0.093sec (1% STDEV)	6.914
100000	6.403sec (1% STDEV)	0.931sec (1% STDEV)	6.878
1000000	63.830 sec (1% STDEV)	9.287 sec (1% STDEV)	6.873

平方根

テストコード

class SurgeSqrtTests: XCTestCase {

    var doubleList: [Double] = [Double]()

    override func setUp() {
        super.setUp()

        let largeNumber = 1000000
        let list = [Int](1...largeNumber)
        doubleList = list.map {i in Double(i)}
    }

    func testSurgeSqrt() {
        self.measureBlock { // Surge フレームワークによる配列の平方根
            let result = Surge.sqrt(self.doubleList) 
        }
    }

    func testNativeSqrt() {
        self.measureBlock { // Swift 標準ライブラリを用いた配列の平方根
            let result = self.doubleList.map(sqrt)
        }
    }
}

largeNumber	Swift	Surge	swift / surge
100	0.002sec (3% STDEV)	0.001sec (30% STDEV)	2.000
1000	0.016sec (5% STDEV)	0.000sec (27% STDEV)	????
10000	0.157sec (2% STDEV)	0.001sec (8% STDEV)	157.000
100000	1.572sec (2% STDEV)	0.007sec (3% STDEV)	224.571
1000000	13.889 sec (1% STDEV)	0.072 sec (2% STDEV)	215.986

累乗

テストコード

class SurgePowTests: XCTestCase {

    var bases = [Double]()
    var exponents = [Double]()

    override func setUp() {
        super.setUp()

        let largeNumber = 100
        bases = [Int](1...largeNumber).map { i in Double(i) }
        exponents = [Double](count: largeNumber, repeatedValue: 2.0)
    }

    func testSurgePow() {
        self.measureBlock { // Surge フレームワークによる配列の累乗
            let result = Surge.pow(self.bases, self.exponents) 
        }
    }

    func testNativePow() {
        self.measureBlock { // Swift 標準ライブラリを用いた配列の累乗
            let result = map(Zip2(self.bases, self.exponents), pow)
        }
    }
}

largeNumber	Swift	Surge	swift / surge
100	0.007sec (3% STDEV)	0.000sec (28% STDEV)	????
1000	0.067sec (3% STDEV)	0.000sec (23% STDEV)	????
10000	0.648sec (2% STDEV)	0.002sec (6% STDEV)	324.000
100000	6.382sec (1% STDEV)	0.008sec (3% STDEV)	797.750
1000000	64.004 sec (1% STDEV)	0.078 sec (1% STDEV)	820.564

---

どの計算に対しても標準的な方法と比較して Surge は相当に早いということが分かります。

計算時間が短いほどSTDEV(標準偏差)が小さいのは、OSの状態が絡んだ処理時間が計算時間が小さければ小さいほど影響を受けやすいためかと思われます。

最後に

CPUによって最適化された計算リソースを活用して、爆速な計算処理が行える事がベンチマークを通じて分かりいただけたでしょうか。

わかりやすくラップされたインターフェイスを活用して計算を素早く行い、快適なアプリを作っていきたいですね！

参考サイト

• mattt/Surge - Github
• 現代のプロセッサと並列実行 - @IT
• [vDSP][信号処理]オーディオ・音声分析への道6 高速フーリエ変換 FFT　その2 - Qiita